package Hot100;

/**
 * @author zhangmin
 * @create 2021-12-22 14:00
 */
public class search33 {
    /**33. 搜索旋转排序数组
     * 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，
     * 使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）
     * 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
     * 二分查找：mid<right，[mid,right]为升序的，mid<target<right则在[mid+1,right]中间查找，否则在[l,mid-1]中查找
     *         mid>=right,[l,mid]为升序的，若l<target<mid则在[l,mid-1]中查找，否则在[mid+1,r]中查找
     * */
    public int search(int[] nums, int target) {
        int n=nums.length;
        if (n==0) return -1;
        if (n==1) return nums[0]==target?0:-1;
        int l=0,r=n-1;
        while (l<r){
            int mid=l+(r-l)/2;
            if (nums[mid]==target) return mid;
            if (nums[mid]<nums[r]){
                if (nums[mid]<target&&target<=nums[r]){
                    l=mid+1;
                }else {
                    r=mid-1;
                }
            }else {
                if (nums[l]<=target&&target<nums[mid]){
                    r=mid-1;
                }else {
                    l=mid+1;
                }
            }
        }
        return nums[l]==target?l:-1;
    }
}
